#define _CRT_SECURE_NO_WARNINGS



typedef char StackDataType;
struct Stack
{
    StackDataType* arr;
    int top;
    int capacity;
};


typedef struct Stack Stack;

void Stackinit(Stack* ps)
{
    assert(ps);
    ps->arr = NULL;
    ps->capacity = ps->top = 0;
}

void Stackpush(Stack* ps, StackDataType x)
{
    assert(ps);
    if (ps->top == ps->capacity)
    {
        int newcapacity = ps->capacity == 0 ? 5 : ps->capacity * 2;
        StackDataType* stackNewNode = (StackDataType*)realloc(ps->arr, newcapacity * sizeof(StackDataType));
        if (stackNewNode == NULL)
        {
            perror("realloc fail!");
            exit(1);
        }
        ps->arr = stackNewNode;
        ps->capacity = newcapacity;
    }
    ps->arr[ps->top++] = x;


}

bool Stackempty(Stack* ps)
{
    assert(ps);
    return ps->top == 0;
}

void Stackpop(Stack* ps)
{
    assert(!Stackempty(ps));
    ps->top--;
}

StackDataType stacktop(Stack* ps)
{
    assert(!Stackempty(ps));
    return ps->arr[ps->top - 1];
}

int stacksize(Stack* ps)
{
    assert(!Stackempty(ps));
    return ps->top;
}
void stackdestroy(Stack* ps)
{
    if (ps->arr)
        free(ps->arr);
    ps->arr = NULL;
    ps->capacity = ps->top = 0;
}
bool isValid(char* s) {
    Stack st;
    Stackinit(&st);
    char* a = s;
    while (*a != '\0')
    {
        if (*a == '(' || *a == '{' || *a == '[')
        {
            Stackpush(&st, *a);

        }
        else
        {
            if (Stackempty(&st))
            {
                stackdestroy(&st);
                return false;
            }
            if ((stacktop(&st) == '{' && *a != '}') ||
                (stacktop(&st) == '[' && *a != ']') ||
                (stacktop(&st) == '(' && *a != ')'))
            {
                stackdestroy(&st);
                return false;
            }
            Stackpop(&st);


        }
        a++;
    }
    if (!Stackempty(&st))
    {
        stackdestroy(&st);
        return false;
    }
    stackdestroy(&st);
    return true;

}